package offerbook;

/**
 * 给定一个数组arr， 返回所有子数组的累加和中， 最小的累加和
 * 方式1：穷举所有子数组，分别求和
 * 方式2：见笔记]
 * 方式3：DP
 * <p>
 * Created at 2019/10/27 0027 下午 10:59
 * {6,-3,-2,7,-15,1,2,2},
 * 连续子向量的最大和为8(从第0个开始,到第3个为止)。
 * 给一个数组，返回它的最大连续子序列的和
 */
public class Code31_MinSumOfSubArray {

    //方式1：穷举
    public static int getMinSum(int[] arr) {
        if (arr == null)
            return 0;
        //遍历所有子串
        int min = 0;
        int res = Integer.MAX_VALUE;
        //当前其实位置为i，则j是从i开始一直到arr.length-1，遍历这中间的所有元素加起来
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                //这里是遍历当前子串的和
                min = 0;
                for (int index = i; index <= j; index++) {
                    min += arr[index];
                }
                //更新子串最小和
                res = Math.min(min, res);
            }
        }
        return res;
    }

    public static int getMinSum1(int[] arr) {
        if (arr == null)
            return 0;
        int cur = 0;
        int max = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {

            cur += arr[i];

            max = Math.min(cur, max);

            if(cur > 0 ){
                cur = 0;
            }
        }
        return max;
    }

    /**
     * DP:
     * f(i)表示以第i个结尾的元素的和,则
     * <p>
     * f(i) = arr[i]  -----f(i-1)>0
     * f(i) = arr[i] + f(i-1) --- f(i-1)<=0
     */
    public static int getMaxSum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int curSum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            // f(i-1)大于0，f(i) = arr[i]
            if (curSum < 0) {
                curSum = arr[i];
            } else {
                curSum += arr[i];
            }

            min = Math.min(curSum, min);
        }
        return min;
    }




}
